//https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        //[0,tail)表示无重复元素的区间,0下标位置的值保留
        int tail = 1;
        for(int i = 0;i<n;i++) //遍历数组,如果和tail-1指向的元素不同,就纳入无重复元素区间
        {
            if(nums[i] != nums[tail-1]) 
                nums[tail++] = nums[i];  
        }
        return tail;//返回nums中唯一元素的个数  [0,tail):共有tail个元素
    }
};

//https://leetcode.cn/problems/merge-sorted-array/
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int end = nums1.size()-1;
        int end1 = end - n ;//nums1有效元素的最后一个位置
        int end2 = n - 1;//nums2有效元素的最后一个位置
        while(end1 >= 0 && end2 >= 0)
        {
            //谁大就放到nums1数组的end位置
            if(nums1[end1] > nums2[end2])
                nums1[end--] = nums1[end1--];
            else 
                 nums1[end--] = nums2[end2--];
        }
        //最后:如果是nums1数组没有遍历结束,那就不需要处理了,因为本来就是要将两个数组的元素归并到nums1当中
        while(end2>=0)
            nums1[end--] = nums2[end2--];
    }
};

//https://leetcode.cn/problems/remove-element/
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int tail = 0;//[0,tail):放的都不是值为val的元素
        for(int i = 0;i<n;i++)
        {
            if(nums[i] != val)
                nums[tail++] = nums[i];
        }
        return tail;//[0,tail):共tail个元素
    }
};

//https://leetcode.cn/problems/rotate-array/
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;//每个元素向右轮转长度次,相当于位置没变

        //三步逆置法
        //前n-k个元素逆置 + 后k个元素逆置 + 整体逆置
        reverse(nums.begin(),nums.begin()+ n - k);
        reverse(nums.begin() + n - k ,nums.end());
        reverse(nums.begin(),nums.end());
    }
};